Page 1 of 15
A Robust Approach to Finding Trustworthy
Influencer in Trust-Oriented E-Commerce
Environments
Feng Zhu1,2, Guanfeng Liu1,2(B)
, Yan Wang3, Mehmet A. Orgun3, An Liu1,2,
Zhixu Li1,2, and Kai Zheng1,2
1 School of Computer Science, Soochow University, 215006 Suzhou, China
{gfliu,anliu,zhixuli,zhengkai}@suda.edu.cn 2 Collaborative Innovation Center of Novel Software Technology
and Industrialization, Nanjing, Jiangsu, China 3 Department of Computing, Macquarie University, Sydney, NSW 2102, Australia
{yan.wang,mehmet.orgun}@mq.edu.au
Abstract. With the recognition of the significance of OSNs (Online
Social Networks) in the recommendation of services in e-commerce, there
are more and more e-commerce platform being combined with OSNs,
forming social e-commerce, where a participant could recommend a prod- uct to his/her friends based on the participant’s corresponding purchas- ing experience. For example, at Epinions, a buyer could share product
reviews with his/her friends. In such platforms, a buyer providing lots
of high quality reviews is very likely to influence many potential buyers’
purchase behaviours. Such a buyer is believed to have strong social influ- ence. However, dishonest participants in OSNs can deceive the existing
social influence evaluation models, by mounting attacks, such as Con- stant (Dishonest advisors constantly provide unfairly positive/negative
ratings to sellers.) and Camouflage (Dishonest advisors camouflage them- selves as honest advisors by providing fair ratings to build up their trust- worthiness first and then gives unfair ratings.), to obtain fake strong
social influence. Therefore, it is crucial to devise a robust social influ- ence evaluation model that can defend against attacks and deliver more
accurate social influence evaluation results. In this paper, we propose a
novel robust Trust-Aware Social Influencer Finding, TrustINF, method
that considers the evolutionary trust relationship and the variations of
historical social influences of participants, which can help deliver more
accurate social influence evaluation results in social e-commerce. Our
experiments conducted on four real social network datasets validate the
effectiveness and robustness of our proposed method, which is greatly
superior to the state-of-the-art method.
1 Introduction
1.1 Background
On trust-oriented e-commerce platforms, like Epinions (epinions.com), after
a transaction, a buyer can provide a review to introduce the quality of the
c Springer International Publishing Switzerland 2016
Q.Z. Sheng et al. (Eds.): ICSOC 2016, LNCS 9936, pp. 387–401, 2016.
DOI: 10.1007/978-3-319-46295-0 24
Page 2 of 15
388 F. Zhu et al.
purchased product and the experience of the transaction. This review is visible
to other buyers, and is much valuable to their decision-making of purchasing. In
addition, a buyer can rate the existing reviews given by others as Not Helpful,
Somewhat Helpful, Helpful, or Very Helpful based on his/her own experiences [1].
If a buyer usually provides Very Helpful product reviews in a specific domain,
like Digital Cameras, his/her recommendation is believed to be trustworthy in
that domain. As indicated in the studies of Social Psychology [2] and Computer
Science [3–5], a buyer is very likely to make a purchase decision following the
recommendations (product reviews) given by trustworthy buyers. Such trust- worthy buyers posses strong influences and can impact many buyers’ purchase
behaviours in a specific domain. These trustworthy buyers are called the advisors
of those participants who trust their product reviews.
1.2 The Problem
In e-commerce environments, a buyer can write product reviews and rate others’
reviews freely, and thus the product review scheme is highly vulnerable to some
typical attacks [1]. For example, in order to obtain a strong influence, a dishonest
advisor can cheat the product review system via some typical attacks, such as
Constant1 and Camouflage2 [6], by (1) recommending a low quality product,
and/or (2) providing an unfair review to a high quality product, each of which
severely harms the benefits of both potential buyers and sellers. The problem of
unfair rating becomes more and more concerned by not only industrial circles
but also academic circles in this filed. Plenty of unfair ratings exist in the reviews
of products, which significantly affect the decision-making of buyers [7,8].
In the literature, the existing influence evaluation methods mainly focus on
studying the influence maximization under the popular linear threshold (LT)
model and independent cascade (IC) model [9], and evaluating social influence
through the process of information diffusion [10]. However, they do not apply any
strategies to defend against the afore-mentioned typical attacks, and thus the
existing models might recommend a participant as an advisor who has obtained
the fake strong social influence by cheating the review systems via the above
mentioned typical attacks. Some methods have been proposed to defend against
collusive [11] or spamming rating attacks [12], which however cannot be directly
applied in defending against the typical Camouflage and Constant attacks in
trust-oriented e-commerce environment. The following Example 1 illustrates the
process of the typical Camouflage attack in e-commerce platforms.
Example 1. Fig. 1 depicts a trust-oriented e-commerce environment, which
contains two sellers S1 and S2 and three buyers B1 to B3. Firstly, B1 and B3
bought the same product (such as digital camera) from S1, so there exist the
transaction relationships between B1 and S1, and between B3 and S1, respec- tively (represented by arrows with dashed lines in Fig. 1). Next, suppose both B1
1 Dishonest advisors constantly provide unfairly positive/negative ratings to sellers. 2 Dishonest advisors camouflage themselves as honest advisors by providing fair rat- ings to build up their trustworthiness first and then gives unfair ratings.
Page 3 of 15
A Robust Approach to Finding Trustworthy Influencer 389
Fig. 1. The camouflage attack
and B3 wrote a review for the camera sold by S1, and they find that their purchase
experiences are similar with each other. Then B1 and B3 trust each other, and
thus there exist trust relationships between B1 and B3 (represented by arrows
with solid lines in Fig. 1). Finally, B2 regards the review of B3 is Very Helpful,
then a trust relationship is established between them. In such a situation, if B2
wants to buy a new camera, B3’s review has a strong influence on B2’s decision
making. But suppose B3 wrote an unfair positive review to the camera sold by
S2, whose camera has a low quality. If B2 wants to buy a new digital camera,
naturally B2 would choose the camera sold by S2 because B2 trusts B3. Then
B2 makes a wrong decision misled by B3’s dishonest action. In such a scenario,
B3 is a Camouflage attacker who establishes fake trustworthiness first and then
misleads other buyers.
The above discussed typical attacks widely exist in trust-oriented e-commerce,
which leads to severe deviation of the reliability of the recommendations [6].
This motivates us to develop a robust influence evaluation method to accurately
find the participants who have real strong influence under the typical attacks
mounted by dishonest buyers in e-commerce environments.
1.3 Contributions
The main contributions of this paper are summarized as follows:
– We propose a novel Trustworthy Influencer Finding method TrustINF based
on the evolutionary trust model [6] and the variations of historical influences
of participants, which can measure the attack probability for each buyer, and
defend against the typical attacks, Constant and Camouflage.
– To the best of our knowledge, this is the first work that defends Camouflage
and Constant attacks in influence evaluation. The proposed TrustINF app- roach is based on Skyline [13] and its time complexity achieves O(n2), where
n is the number of buyers in e-commerce environments.
Page 4 of 15
390 F. Zhu et al.
– We have conducted experiments on the four real social e-commerce datasets,
i.e., Epinions, Slashdot, Amazon and BeerAdvocate. The average Attacker
Identification Ratios of our TrustINF under Constant attack and Camouflage
attack achieve 66.33 % and 81.33 % respectively. On average, our Trust-IMM
can improve the robustness of IMM by 85.82 %.
2 Related Work
In the literature, according to different influence problems, we categorize them
as influence maximization, individual influence evaluation and the unfair rating
identification in influence evaluation.
Influence maximization is to find important applications in viral marketing
[14], where a product provider selects K influencers in an OSN and provides
them with incentives (e.g., free samples) to accept a new product, excepting
the social influence of these influencers can work and attract more potential
users. [15] propose an algorithm that has a simple tunable parameter, for users
to control the balance between the running time and the influence spread. [16]
propose an algorithm IRIE that integrates the advantages of influence ranking
(IR) and influence estimation (IE) methods. [17] provide a scalable influence
approximation algorithm, Independent Path Algorithm (IPA). [18] investigate a
novelty decay phenomenon where the influence of a participant decays with the
increase of the number of sending the same message to others in OSNs. Then
they [19] investigate the effect of the novelty decay in the influence maximization
in OSNs. Recently, [20] proposed an algorithm which is based on martingales, a
classic statistical tool, to support a larger class of information diffusion model
over the existing methods. Moreover, [21] propose a local influence maximization
problem. This problem is to find a group of nodes that have the maximal impact
on a specified participant. In addition, [22] propose a probabilistic model to
discover the latent influence between participants in OSNs.
In individual social influence evaluation, [23] propose an approach, called
SoCap, to find influencers in OSNs by using the social capital value. They model
the problem of finding influencers in OSNs as a value-allocation problem, where
the allocated value denotes the individual social capital. In addition, [24] pro- pose a method to identify influential agents in open multi-agent systems with- out centralised control and individuals have equal authority. The above existing
methods in influence evaluation did not consider any strategies defending against
attacks, and thus are vulnerable to the attacks, like Camouflage and Constant,
from dishonest participants.
In order to identify the unfair ratings and improve the robustness of influ- ence evaluation models, some approaches [11,12] have been proposed to defend
against the collusive and the spamming rating attacks respectively in trust- oriented e-commerce environments. However, their methods cannot be used
directly to defend against the Camouflage and Constant attacks that widely
exist in e-commerce environments.
Page 5 of 15
A Robust Approach to Finding Trustworthy Influencer 391
3 Preliminary
3.1 Trust Relationship
In e-commerce environments, a Trust Relationship is a relationship between a
buyer and an advisor, which illustrate the probability of a buyer who will make
the purchase decision based on the reviews of the advisor. This type of trust
relationship widely exist in trust-oriented e-commerce, like Epionions, Amazon,
FilmTrust, etc. Let Ti,j to denote the trust relationship between Bi and Bj .
3.2 Transaction Relationship
In trust-oriented e-commerce environment, a Transaction Relationship is a rela- tionship between a buyer and a seller when they have at least one transaction. Let
Ri,j denote the transaction relationship between Bi and Sj . If Bi have bought
m items from Sj , and the rating values to those m items are ri,j = {r1
i,j , ..., rm
i,j},
m > 0, then
Ri,j = 1
m
m
k=1
rk
i,j . (1)
3.3 Evolutionary Trust Model
The Evolutionary Trust Model [6] is usually used to cope with unfair rating
attacks from dishonest advisors. By using this model, if a buyer finds the real
transactional experience is different with the reviews given by an advisor, the
buyer could evolve his/her trust relationships to absorb the advisors whose
reviews better match the buyer’s purchase experience and distrust the previous
advisor whose review is not recognized by the buyer. The following Example 2
illustrates the evolutionary process.
Example 2. In Fig. 2, suppose there is a low rating given by B2 to S2 (i.e.,
R2,2 = 0.2), which is quite different with B3’s review with R3,2 = 1.0. Then
B2 evolves his/her trust relationships to form a new trust relationship T2,1 =
1.0 with B1 as B1’s review with R1,1 = 0.2 matches B2’s purchase experience.
Meanwhile B2 removes the trust relationship with B3. Finally, B1 becomes a new
advisor of B2. This process is called the Trust Evolution.
The below fitness function in Eq. (2) is used for buyers to measure the quality
of their trust networks by comparing the two types of derived reputation values
of sellers [6].
f(V Ti) = 1
m
m
j=1
|Ri,j − Ri,j | (2)
where m is the number of sellers who have been rated by both Bi and Bi’s
advisors. Ri,j = 1
|A(Bi)|
|A(Bi)|
k=1 Rk,j denotes the average rating value given
Page 6 of 15
392 F. Zhu et al.
Fig. 2. Evolutionary process
by Bi’s advisors to seller Sj . f(V Ti) means that the little difference of ratings
given by a buyer and his/her advisors illustrating the high quality of their trust
relationship.
The following Eq. (3) is used to measure the difference of trust relationships
between two buyers Bi and Bj .
diff(V Ti,VTj ) = 1
m
m
k=1
|Ti,k − Tj,k| (3)
where m is the number of both Bi’s and Bj ’s advisors; it reflects the difference
between the trust relationships of Bi and Bj . The less the value of diff(V Ti,VTj )
the less the difference of the trust value from Bi and Bj to their common advisors.
Equation (4) is used to measure the difference of fitness.
diff(f(V Ti), f(V Tj )) = |f(V Ti) − f(V Tj )| (4)
In evolutionary process, a function δ(·) is used to judge the compatibility of new
trust relationship resource and calculated as follows:
δ(V Ti,VTj ) =(diff(V Ti,VTj ) − 0.5)
× (diff(f(V Ti), f(V Tj )) − 0.5) (5)
Here, we set threshold as 0, only when two buyers Bi and Bj satisfy
δ(V Ti,VTj ) > 0.
4 Impact Factors of Influence
With adopting the Evolutionary Trust Model, we propose two impact factors
which have significant impact on real influence evaluation of participants in
e-commerce.
Page 8 of 15
394 F. Zhu et al.
Algorithm 1. TrustINF
Input: Buyer set B, the parameter sets of all buyers X, the number of buyer set n;
Output: The set of probability of attack of all buyers P = {Pi};
1: P ←− ∅;
2: N ←− ∅ /* The dominating numbers of buyers */
3: N ←− ∅ /* The numbers dominated by other buyers for all buyers */
4: for each Xi in X do
5: for each Xj in X, j = i do
6: /* Confirming whether Xi dominates Xj , which is based on Definition 1 */
7: m = 0;
8: f lag = false;
9: for k = 1 to 4 do
10: if (Xk
i > Xk
j ) then
11: m + +;
12: f lag = true;
13: end if
14: if (Xk
i == Xk
j ) then
15: m + +;
16: end if
17: end for
18: if (m == 4 and f lag) then
19: Ni + +;
20: N
j + +; /* Bj is dominated by Bi */
21: end if
22: end for
23: end for
24: for each Bi in B do
25: Pi = (N
i − Ni)/(n − 1)
26: end for
27: Return P;
function Sp
i is continuous and differentiable, as we know, based on the method
of two variables’ function extremum, the minimization point of Sp
i makes the
first derivative of function Sp
i be zero, and the second derivative positive, which
could be easily proved by Taylor formula for function of two variables [26]. For
this purpose, we differentiate Sp
i with respect to k and b, and set the results to
zero. Then we can obtain:
k = gradi = (−u − u2 + 4)/2 (9)
and
b = Sf − kSt
n , (10)
where u = pSf2−S2
f +S2
t −pSt2
Sf St−pSf t , Sf2 = p
j=1(xj
i )2, Sf = p
j=1 xj
i , St = p
j=1 tj ,
St2 = p
j=1 t
2
j and Sf t = p
j=1 xj
i · tj .
Page 12 of 15
398 F. Zhu et al.
Fig. 4. The Attacker Identification on the four datasets. The color of each block reflects
the proportion of the attackers in different ranges of ranking. (Color figure online)
Parameters in IMM and Diffusion Models. In this paper, we adopt two
typical diffusion models, i.e., Linear Threshold (LT) model [29] and Independent
Cascade (IC) model [9] to investigate the performance of Trust-IMM.
– IMM: IMM [20] is an influence maximization algorithm which adopts sam- pling method to return an approximate solution under the triggering model.
In this experiments, we consider two kinds of triggering models, i.e., LT and
IC. For IMM, we set ε = 0.5, = 1, and K ∈ [10, 20, 30, 40, 50].
– Linear Threshold (LT) Model: LT model is the first model to imitate the
diffusion process of information. The approach is based on the node-specific
thresholds [29]. In the model, at time step t, all buyers that were influenced
in step t − 1 remain being influenced. A buyer Bi is influenced based on a
monotonic function of its influenced neighbors f(In(i, t)) ∈ [0, 1] (see Eq. (16))
and a threshold θi ∈ [0, 1], i.e., Bi is influenced at time t if f(In(i, t)) ≥ θi.
f(In(i, t)) =
Bj∈In(i,t)
bi,j (16)
where In(i, t) is the influenced neighbors of Bi at time step t. Here, we set
bi,j = Ti,j/
Bk∈Adi Ti,k; Adi is the advisor of Bi and
Bj∈Adi bi,j ≤ 1.
Page 15 of 15
A Robust Approach to Finding Trustworthy Influencer 401
5. Liu, G., Wang, Y., Orgun, M.A.: Social context-aware trust network discovery in
complex contextual social networks. In: AAAI, pp. 101–107 (2012)
6. Jiang, S., Zhang, J., Ong, Y.S.: An evolutionary model for constructing robust
trust networks. In: AAMAS, pp. 813–820 (2013)
7. Liu, A., Zheng, K., Li, L., Liu, G., Zhao, L., Zhou, X.: Efficient secure similarity
computation on encrypted trajectory data. In: ICDE 2015, pp. 66–77 (2015)
8. Liu, A., Li, Q., Huang, L., Xiao, M.: Tolerant composition of transactional web
services. IEEE Trans. Serv. Comput. 3(1), 46–59 (2010)
9. Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the spread of influence through ́
a social network. In: KDD, pp. 137–146 (2003)
10. Kimura, M., Saito, K.: Tractable models for information diffusion in social net- works. In: PKDD, pp. 259–271 (2006)
11. Wang, D., Muller, T., Zhang, J., Liu, Y.: Quantifying robustness of trust systems
against collusive unfair rating attacks using information theory. In: IJCAI, pp.
111–117 (2015)
12. Gao, J., Dong, Y., Shang, M., Cai, S., Zhou, T.: Group-based ranking method for
online rating systems with spamming attacks. Europhys. Lett. (2015)
13. Borzsonyi, S., Kossmann, D., Stocker, K.: The skyline operator. In: ICDE, pp.
421–430 (2001)
14. Domingos, P., Richardson, M.: Mining the network value of customers. In: KDD,
pp. 57–66. ACM (2001)
15. Chen, W., Wang, C., Wang, Y.: Scalable influence maximization for prevalent viral
marketing in large-scale social networks. In: KDD, pp. 1029–1038 (2010)
16. Jung, K., Heo, W., Chen, W.: IRIE: Scalable and robust influence maximization
in social networks. In: ICDM, pp. 918–923 (2012)
17. Kim, J., Kim, S.K., Yu, H.: Scalable and parallelizable processing of influence
maximization for large-scale social networks? In: ICDE, pp. 266–277 (2013)
18. Ver Steeg, G., Ghosh, R., Lerman, K.: What stops social epidemics? In: ICWSM
(2011)
19. Feng, S., Chen, X., Cong, G., Zeng, Y., Chee, Y.M., Xiang, Y.: Influence maxi- mization with novelty decay in social networks. In: AAAI, pp. 37–43 (2014)
20. Tang, Y., Shi, Y., Xiao, X.: Influence maximization in near-linear time: a martin- gale approach. In: SIGMOD, pp. 75–86. ACM (2015)
21. Guo, J., Zhang, P., Zhou, C., Cao, Y., Guo, L.: Personalized influence maximization
on social networks. In: CIKM, pp. 199–208 (2013)
22. Iwata, T., Shah, A., Ghahramani, Z.: Discovering latent influence in online social
activities via shared cascade Poisson processes. In: KDD, pp. 266–274 (2013)
23. Subbian, K., Sharma, D., Wen, Z., Srivastava, J.: Finding influencers in networks
using social capital. In: ASONAM, pp. 592–599 (2013)
24. Franks, H., Griffiths, N., Anand, S.S.: Learning influence in complex social net- works. In: AAMAS, pp. 447–454 (2013)
25. Li, L., Wang, Y.: A trust vector approach to service-oriented applications. In:
ICWS, pp. 270–277 (2008)
26. Okelo, B., Boston, S., Minchev, D.: Advanced Mathematics The Differential Cal- culus for Multi-variable Functions. LAP Lambert Academic, Saarbr ̈ucken (2012)
27. Velichenko, V.V.: Sufficient conditions for absolute minimum of the maximal func- tional in the multi-criterial problem of optimal control. In: Marchuk, G.I. (ed.)
Optimization Techniques 1974. LNCS, vol. 27, pp. 220–225. Springer, Heidelberg
(1975)
28. Chan, C.Y., Jagadish, H., Tan, K.L., Tung, A.K., Zhang, Z.: Finding k-dominant
skylines in high dimensional space. In: SIGMOD, pp. 503–514 (2006)
29. Granovetter, M.: Threshold models of collective behavior. Am. J. Soci. 83(6),
1420–1443 (1978)